from typing import List


class Solution1:
    def partition(self, nums: List, low, high):
        i = low - 1
        pivot = nums[high]

        for j in range(low, high):
            if nums[j] <= pivot:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]
        nums[i+1], nums[high] = nums[high], nums[i+1]
        return i + 1

    def sort(self, nums: List[int], low, high):
        if low < high:
            idx = self.partition(nums, low, high)

            self.sort(nums, low, idx-1)
            self.sort(nums, idx+1, high)


class Solution2:
    def func(self, s: str) -> str:
        length = len(s)
        idx1, idx2 = 0, 0

        for i in range(length - 1):
            for j in range(i, length, 2):
                if s[i:j].count('0') == s[i:j].count('1') and (j - i) > (idx2 - idx1):
                    # if (j-i) % 2 == 1:
                    #     continue
                    idx1, idx2 = i, j

        return s[idx1:idx2]


class Solution3:
    def func(self, s: str) -> bool:
        left_set = {'(', '[', '{'}
        right_set = {')', ']', '}'}
        cor_dic = {'(': ')', '[': ']', '{': '}'}

        temp = ''
        for x in s:
            if x in left_set or x in right_set:
                temp += x
        stack = [0]
        for letter in temp:
            if letter in left_set:
                stack.append(letter)

            if letter in right_set:
                if len(stack) == 1:
                    return False
                if letter == cor_dic[stack[-1]]:
                    stack.pop()
            else:
                continue
        if len(stack) == 1:
            return True
        return False


if __name__ == '__main__':
    print()
    # nums = [-1,-2,1,2,2,9,8,7,6,5,4,1]
    # length = len(nums)
    # sort(nums, 0, length-1)
    # print(nums)